De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat

vragen bekijken

een vraag stellen

hulpjes

zoeken

FAQ

links

twitter

boeken

help

inloggen

colofon

Reageren...

Re: Inverse matrix

Gegeven is een ongerichte graaf G met knopen V en kanten E, en een knopenbedekking X. Gevraagd is om een koppeling K te vinden van minimale kardinaliteit waarbij de eindpunten van de kanten in de koppeling een superset vormen van C. Bovendien moet K worden gevonden in polynomiale tijd in de grootte van de invoer.

Ik heb geprobeerd om hier een recursieve formule van te maken, waarbij ik alle deelverzamelingen van E bekijk. Namelijk, door voor elke knoop in C uit te proberen welke aangrenzende kant ik neem. Aangezien ik nog niet weet wat optimaal is, probeer ik alle aangrenzende kanten. Dit is echter exponentieel in E, aangezien ik alle deelverzamelingen van E moet bekijken. Er lijkt een veel eenvoudigere oplossing voor dit probleem aangezien een koppeling en bedekking erg gerelateerd zijn aan elkaar. Echter loop ik hierop vast. Hulp is gewenst.

Antwoord

Zoals het nu geformuleerd is zal het niet lukken: een koppeling pakt een even aantal knopen. Als $C$ uit alle knopen bestaat, dus $C=V$, en als er een oneven aantal knopen is dan pakt de koppeling zeker niet alle knopen mee.

Er moeten dus voorwaarden bij: over de aard van de overdekking, over de aard van de graaf, ...

Gebruik dit formulier alleen om te reageren op de inhoud van de vraag en/of het antwoord hierboven. Voor het stellen van nieuwe vragen kan je gebruik maken van een vraag stellen in het menu aan de linker kant. Alvast bedankt!

Reactie:
	Klik eerst in het tekstvlak voordat je deze knopjes en tekens gebruikt. Pas op: onderstaande knopjes en speciale karakters werken niet bij ALLE browsers! áâæàåãäßçéêèëíîìïñóôòøõöúûùüýÿ½¼¾€£®© $\forall$$\exists$$\neg$$\wedge$$\vee$$\Leftrightarrow$$\Leftarrow$$\Rightarrow$$\emptyset$$\cap$$\cup$$\supset$$\supseteq$$\not\subset$$\subset$$\subseteq$$\in$$\notin$ $\sim$$\equiv$$\ne$$\pm$$\times$$\div$$\otimes$$\oplus$$\pi$$\leftarrow$$\uparrow$$\to$$\downarrow$ $\sqrt{}$$\sum$$\prod$$\infty$$\smallint$$\Delta$$\nabla$$\partial$$\angle$$\bot$$\cong$$\widehat p$ $\alpha$$\beta$$\gamma$$\delta$$\varepsilon$$\phi$$\theta$$\lambda$$\mu$$\rho$$\sigma$$\tau$$\omega$$\chi$$\Gamma$$\vartheta$$\Lambda$$\Omega$$\Psi$$\zeta$ $\mathbf{N}$ $\mathbf{Z}$ $\mathbf{Q}$ $\mathbf{R}$ $\mathbf{C}$
Categorie:	Rekenmachine
Ik ben:	-------------- Maak een keuze --------------- Leerling onderbouw vmbo-havo-vwo Leerling bovenbouw vmbo Leerling bovenbouw havo-vwo Leerling mbo Student hbo Student universiteit 1ste graad ASO-TSO-BSO Overige TSO-BSO 2de graad ASO 3de graad ASO Student Hoger Onderwijs België Student universiteit België Cursist vavo Docent Ouder Iets anders Beantwoorder
Naam:
Emailadres:
Datum:	19-5-2024